1. Field of the Invention
The present invention relates generally to streaming packets of information, and in particular, to a method, apparatus, and article of manufacture for packet erasure/error correction coding with a nested receiver structure.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Embodiments of the invention evaluate packet erasure/error correction coding with a nested receiver structure, where the set of packets received by each receiver i is a subset of that received by the next receiver i+1. A natural setting in which this type of structure arises is with temporal demands: each receiver corresponds to a particular deadline in the received packet stream by which a particular piece of information must be decoded, and has access to all earlier observations. The protocol can specify an arbitrary set of deadlines and demands.
The prior art fails to provide the ability to construct codes that can correct any z packet erasures (or errors) for all feasible information rates, without a priori knowledge of which packets will be erased (erroneous). By making a connection with prior work (of the inventors of the present application) on non-multicast network error correction, one may characterize the capacity region of feasible demand vectors for any given nested structure (set of deadlines) and any z erasures (errors). In particular, embodiments of the invention provide a capacity-achieving coding scheme where no coding occurs across information demanded by different receivers.
The network error correction problem, where transmissions on an unknown set of z links are arbitrarily corrupted, was introduced by Cai and Yeung ([1], [2], and [3]) for single-source multicast. They characterized the capacity region and showed a connection between network error correction and network erasure correction by generalizing classical coding theory to the network setting. Network coding for multicast packet erasure correction was considered in [4] and [5]. The problem of multicast non-coherent error correction, where the network topology and/or network code are not known a priori, was studied in [6], [7], [8].
For non-multicast networks, finding the capacity region of a general network even without errors is an open problem. The error-free capacity regions for some special cases, such as single-source two-sink networks ([9], [10], [11]) and single-source disjoint- or nested-demand networks ([12]) with multiple sinks, are given by the cutset bounds. On the other hand, examples of non-multicast networks whose error-free capacity regions are not given by cutset bounds appear in [13] and [14].
For non-multicast error correction, prior work of the present inventors [15] has shown that unlike the error-free case, cutset bounds are loose in general for single-source two-sink networks with errors, and refined bounds were developed for non-multicast networks. Embodiments of the present invention build on some of the techniques developed in that work.
[16]-[17] has constructed streaming codes that minimize the delay required to correct burst errors of given length.